package org.ww.algorithm.sort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int arr[]={-999,33,-1,23323,12};
//        adjustHeap(arr,1,5);
//        System.out.println(Arrays.toString(arr));
//
//        adjustHeap(arr,0,5);
//        System.out.println(Arrays.toString(arr));
        //进行大顶堆调整
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        int temp=0;
        for(int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;
            adjustHeap(arr,0,j);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 调整大顶堆
     * @param arr  数组
     * @param i 最后一个非叶子节点索引
     * @param length 排序数组的长度
     */
    public static void adjustHeap(int arr[],int i,int length){
        int temp=arr[i];

        for(int k=i*2+1;k<length;k=k*2+1){
            if(k+1<length && arr[k]<arr[k+1]){
                k++;
            }
            if(arr[k]>temp){
                arr[i]=arr[k];
                i=k;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }
}
